Search results for "Subset sum problem"
showing 6 items of 6 documents
Binary Hamming codes and Boolean designs
2021
AbstractIn this paper we consider a finite-dimensional vector space $${\mathcal {P}}$$ P over the Galois field $${\text {GF}}(2),$$ GF ( 2 ) , and the family $${\mathcal {B}}_k$$ B k (respectively, $${\mathcal {B}}_k^*$$ B k ∗ ) of all the k-sets of elements of $$\mathcal {P}$$ P (respectively, of $${\mathcal {P}}^*= {\mathcal {P}} \setminus \{0\}$$ P ∗ = P \ { 0 } ) summing up to zero. We compute the parameters of the 3-design $$({\mathcal {P}},{\mathcal {B}}_k)$$ ( P , B k ) for any (necessarily even) k, and of the 2-design $$({\mathcal {P}}^{*},{\mathcal {B}}_k^{*})$$ ( P ∗ , B k ∗ ) for any k. Also, we find a new proof for the weight distribution of the binary Hamming code. Moreover, we…
On the subset sum problem for finite fields
2021
Abstract Let G be the additive group of a finite field. J. Li and D. Wan determined the exact number of solutions of the subset sum problem over G, by giving an explicit formula for the number of subsets of G of prescribed size whose elements sum up to a given element of G. They also determined a closed-form expression for the case where the subsets are required to contain only nonzero elements. In this paper we give an alternative proof of the two formulas. Our argument is purely combinatorial, as in the original proof by Li and Wan, but follows a different and somehow more “natural” approach. We also indicate some new connections with coding theory and combinatorial designs.
Affine Automata Verifiers
2021
We initiate the study of the verification power of Affine finite automata (AfA) as a part of Arthur-Merlin (AM) proof systems. We show that every unary language is verified by a real-valued AfA verifier. Then, we focus on the verifiers restricted to have only integer-valued or rational-valued transitions. We observe that rational-valued verifiers can be simulated by integer-valued verifiers, and their protocols can be simulated in nondeterministic polynomial time. We show that this upper bound is tight by presenting an AfA verifier for NP-complete problem SUBSETSUM. We also show that AfAs can verify certain non-affine and non-stochastic unary languages.
A genetic algorithm for the minimum generating set problem
2016
Graphical abstractDisplay Omitted HighlightsWe propose a novel formulation for the MGS problem based on multiple knapsack.The so-conceived MGS problem is solved by a novel GA.The GA embeds an intelligent construction method and specialized crossover operators.We perform a thorough comparison with regards to state-of-the-art algorithms.The proposal proves to be very competitive, specially for large and hard instances. Given a set of positive integers S, the minimum generating set problem consists in finding a set of positive integers T with a minimum cardinality such that every element of S can be expressed as the sum of a subset of elements in T. It constitutes a natural problem in combinat…
Dynamic programming and Munkres algorithm for optimal photovoltaic arrays reconfiguration
2015
Abstract In this paper, an original formulation of the control problem for optimal PV array reconfiguration, following a Total Cross Tied layout, is proposed. The formulation follows the well-known subset sum problem, which is a special case of the knapsack problem. The reconfiguration is a measure devoted to mitigate the mismatch effect and maximize the output power of small photovoltaic plants under non-homogeneous working conditions. Therefore, reconfiguration means changing the connections of the solar panels adaptively by a dynamic switching matrix. The control system implements an easy dynamic programming algorithm to change the switches layout. The use of the Munkres assignment metho…
Permutations of zero-sumsets in a finite vector space
2020
Abstract In this paper, we consider a finite-dimensional vector space 𝒫 {{\mathcal{P}}} over the Galois field GF ( p ) {\operatorname{GF}(p)} , with p being an odd prime, and the family ℬ k x {{\mathcal{B}}_{k}^{x}} of all k-sets of elements of 𝒫 {\mathcal{P}} summing up to a given element x. The main result of the paper is the characterization, for x = 0 {x=0} , of the permutations of 𝒫 {\mathcal{P}} inducing permutations of ℬ k 0 {{\mathcal{B}}_{k}^{0}} as the invertible linear mappings of the vector space 𝒫 {\mathcal{P}} if p does not divide k, and as the invertible affinities of the affine space 𝒫 {\mathcal{P}} if p divides k. The same question is answered also in the case where …